package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/1/12 10:28
 * @description：https://leetcode-cn.com/problems/increasing-triplet-subsequence/
 */
public class 递增的三元子序列 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.increasingTriplet(new int[]{2,1,5,0,7,6}));
    }

    // 贪心
    /*
    class Solution {
        public boolean increasingTriplet(int[] nums) {
            int first = nums[0];
            int second = -1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] > first) {
                    if (nums[i] > second && second != -1) return true;
                    second = nums[i];
                } else {
                    first = nums[i];
                }
            }
            return false;
        }
    }
     */

    class Solution {
        public boolean increasingTriplet(int[] nums) {
            int n = nums.length;
            if (n < 3) return false;
            int[] leftNs = new int[n];
            leftNs[0] = nums[0];
            int[] rightNs = new int[n];
            rightNs[n - 1] = nums[n - 1];
            for (int i = 1; i < n; i++) {
                leftNs[i] = Math.min(leftNs[i - 1], nums[i]);
            }
            for (int i = n - 2; i >= 0; i--) {
                rightNs[i] = Math.max(rightNs[i + 1], nums[i]);
            }
            for (int i = 1; i < n - 1; i++) {
                if (nums[i] > leftNs[i - 1] && nums[i] < rightNs[i + 1]) return true;
            }
            return false;
        }
    }
}
